COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	multiv[e81,jmc]		Multiple valued functions in LISP
C00008 ENDMK
C⊗;
multiv[e81,jmc]		Multiple valued functions in LISP

	The proposals for multiple valued functions in the 1981 July 24
version of the COMMON LISP proposal outlaw the neatest ways
of writing certain multiple valued functions by virtue of the restriction
that only the first argument is used when such a function is used
as an argument.  It would be best not to define the multiple value
conventions yet until the issues can be decided.

	We give some examples to illustrate the point.

	1. The following function computes the gcd of two numbers  m
and  n  with  n  the smaller.  It also computes the co-efficients
a  and  b such that  the gcd is  am+bn.

	gcd(m,n) <=	if n=0 then m,1,0
			else {m/n}[lambda q r. {gcd(n,r)}
				[lambda g a b. g,b,a-qb]].

In internal notation, i.e. in list notation, this is

(defun gcd (m n) (if
		  (zerop n)
		  (values m 1 0)
		  ((lambda (q r) ((lambda (g a b) (values g b (- a (* q b))))
				  (gcd n r)))
		   (/ m n))))

Herein the fucntion  /  is considered to produce two values (quotient and
remainder), and the gcd itself produces three (the gcd itself and the
two co-efficients).

2. The function  (mapalong f l u)  like  (mapcar f l)  in making a
list obtained by applying the function  f  successively to the elements
of the list  l.  However,  f  has two arguments, the second of which is
a state  u, and two outputs, the second of which is a new state.  Thus
we have

(defun mapalong (f l u)
       (if (null l) (values nil u)
	   ((lambda (e u1)
		    ((lambda (l1 u2) (values (cons e l1) u2))
		     (mapalong f (cdr l) u1)))
	    (f (car l) u)))).

3. mapalong is used to make an expression rewriter that keeps a list
of subexpression that can't be rewritten any more.  We have

(defun rewrite (e u) (if
		      (member e u)
		      (values e u)
		      (if (atom e)
			  ((lambda (e1) (if (= e1 e)
					    (values e (cons e u))
					    (rewrite e1 u)))
			   (rewtop e))
			  ((lambda (l u1)
				   ((lambda (e1)
					    ((lambda (e2)
						     (if (= e2 e1)
							 (values e1 u1)
							 (rewrite e2 u1)))
					     (rewtop e1)))
				    (mkexp (op e) l)))
			   (mapalong (components e) rewrite u)))))


In the above,  (rewtop e)  rewrites the expression  e  at the top level,
(component e) is a list of the subexpressions of  e, (op e) is the
operation or function part of  e, and  (mkexp op l)  makes an expression
with given  op  and components.


4. (count x n u) counts the number of cells in a possible re-entrant
list structure  x  considering the cells listed in  u  to have already
been counted and  n  to have been found.  We have


(defun count (x n u) (if (memq x u)
			 (values n u)
			 (atom x)
			 (values (add1 n) (cons x u))
			 (count (car x) (count (cdr x) (add1 n) (cons x u))))).

Notice that the inner occurrence of  count  serves as two of the
arguments of the outer occurrence.